package sort;


import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {0, 5, 7, 1, 3, 2, 9, 8, 6, 10, 4};

        sort(arr, 0, arr.length - 1);//快速排序
        System.out.println(Arrays.toString(arr));

        rSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }


    public static void sort(int[] arr, int i, int j) {
        if (i >= j) {
            return;
        }
        int baseNum = arr[i];//基准数
//      1  2 3 4 5 6 7
        //寻找基准数插入的位置
        int left = i;
        int right = j;
        while (left < right) {
//            System.out.println(baseNum + "left=" + left + " right=" + right + Arrays.toString(arr));
            while (left < right && arr[right] >= baseNum) {//后往前
                right--;
            }
            while (left < right && arr[left] <= baseNum) {//前往后
                left++;
            }
            //交换位置
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }//right即为基准数的位置
        //基准数归位
        arr[i] = arr[right];
        arr[right] = baseNum;
        //递归
        sort(arr, i, right - 1);
        sort(arr, right + 1, j);
    }

    public static void rSort(int[] arr, int i, int j) {
        if (i >= j) {
            return;
        }
        int baseNum = arr[i];
        int left = i;
        int right = j;

        while (left < right) {
            System.out.println("baseNum=" + baseNum + " left=" + left + " right=" + right + Arrays.toString(arr));

            while (left < right && arr[right] <= baseNum) {//找比基准数大的数
                right--;
            }
            while (left < right && arr[left] >= baseNum) {//找比基准数小的数
                left++;
            }

            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        arr[i] = arr[right];
        arr[right] = baseNum;

        rSort(arr, i, left - 1);
        rSort(arr, left + 1, j);
    }
}
